package BFS解决FloodFill算法.解决拓扑排序;

import java.lang.invoke.WrongMethodTypeException;
import java.util.*;

public class 火星词典 {

    Map<Character, Set<Character>> edges = new HashMap<>();// 邻接表
    Map<Character,Integer> in = new HashMap<>();// 统计每个节点的入度
    boolean check ;

    public String alienOrder(String[] words)
    {
        // 1.初始化入度哈希表+建图
        for(String s : words)
        {
            for(int i = 0 ;i<s.length();i++)
            {
                char ch = s.charAt(i);
                in.put(ch,0);
            }
        }

        int n = words.length;
        for(int i = 0;i <n;i++)
        {
            for(int j = i+1;j<n;j++)
            {
                add(words[i],words[j]);
                if(check == true) return "";
            }
        }

        // 2. 拓补排序
        Queue<Character> q= new LinkedList<>();
        for(char ch : in.keySet())
        {
            if(in.get(ch) == 0) q.add(ch);
        }
        StringBuffer ret = new StringBuffer();
        while(!q.isEmpty())
        {
            char ch = q.poll();
            ret.append(ch);
            for(char next : edges.get(ch))
            {
                in.put(next,in.get(next)-1);
                if(in.get(next) == 0 ) q.add(ch);
            }
        }

        //3.判断
        for(char ch  : in.keySet())
        {
            if(in.get(ch) != 0) return "";

        }
        return ret.toString();


    }
    public void add(String a,String b)
    {
        int n = Math.min(a.length(),b.length());
        int i = 0;
        for(;i<n;i++)
        {
            char c1 = a.charAt(i),c2 = b.charAt(i);
            if(c1 != c2)
            {

                if(!edges.containsKey(c1))
                {
                    edges.put(c1,new HashSet<>());
                }
                if(!edges.get(c1).contains(c2))
                {
                    edges.get(c1).add(c2);
                    in.put(c2,in.get(c2)+1);
                }
                break;
            }
        }
        if(i == b.length() && i< a.length()) check =true;
    }
}
